package net.entelijan.cobean.tree.pathfind;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

import net.entelijan.cobean.tree.IPathFinder;
import net.entelijan.cobean.tree.IPathFinderNode;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**
 * A simple implementation of the IPathfinder without any caching. Suitable for
 * small trees.
 * 
 */
public class RecursivePathFinder implements IPathFinder {

	private static Log log = LogFactory.getLog(RecursivePathFinder.class);

	public RecursivePathFinder() {
		super();
	}

	@SuppressWarnings({ "unchecked", "rawtypes" })
	@Override
	public List<?> findPath(IPathFinderNode root, Object value) {
		return new ArrayList(findPathInternal(root, value));
	}

	private Deque<IPathFinderNode> findPathInternal(IPathFinderNode root,
			Object value) {
		if (log.isDebugEnabled()) {
			log.debug("[findPath] root='" + root + "' value='" + value + "'");
		}
		Deque<IPathFinderNode> re = null;
		if (root.getModel().equals(value)) {
			re = new ArrayDeque<IPathFinderNode>();
			re.add((IPathFinderNode) root);
		} else {
			for (int i = 0; i < root.getChildCount(); i++) {
				IPathFinderNode c = (IPathFinderNode) root.getChildAt(i);
				Deque<IPathFinderNode> subPath = findPathInternal(c, value);
				if (subPath != null) {
					subPath.addFirst(root);
					re = subPath;
				}
			}
		}
		return re;
	}

}
